package greed;

import java.util.Arrays;

/**
 * @Classname : TaskScheduler
 * @Description : 621. 任务调度器
 * https://leetcode.cn/problems/task-scheduler/
 * @Author : cty
 * @Date 2023/4/22 22:08
 */


public class TaskScheduler {
    public int leastInterval(char[] tasks, int n) {
        // 统计每个元素出现次数
        int[] table = new int[26];
        for (char task : tasks) table[task - 'A']++;
        Arrays.sort(table);
        // 找到出现次数最多的任务，计算最短时间
        // 如任务A出现最多次数3，n为2：AxxAxxA
        int min = (n + 1) * (table[25] - 1) + 1;
        // 出现次数最多的任务每多1个，则最短时间加1
        for (int i = 24; i >= 0; i--) {
            if (table[i] < table[25]) break;
            min++;
        }
        // 若剩余任务填充不完待填充位置x，则最短时间为min
        // 若剩余任务填充完待填充位置x还有剩余，则剩余任务可以放在位置-处：Axx-Axx-A，此时最短时间为任务的总个数
        return Math.max(min, tasks.length);
    }
}
